| 翻訳と辞書 |
| PCP (計算複雑性理論) ： ウィキペディア日本語版 |
PCP (計算複雑性理論)
計算複雑性理論における PCP とは、確率的検査可能証明（probabilistically checkable proof）系を持つ決定問題の複雑性クラスである。
== 概要と定義 ==
計算複雑性理論において、PCP 系は対話型証明系の一種と見ることができ、証明者がメモリを持たない神託機械であり、検証者が多項式時間の乱択アルゴリズムである。ある言語に属する入力（すなわち答えがYES）の場合、検証者が確実に受理する神託（証明）が存在する。答えがNOの入力の場合、神託がどうであれ、検証者はそれを少なくとも1/2の確率で拒絶する（co-RP参照）。
PCP の別の見方として、NP の強力版と見ることもできる。NPに属する言語について、証明の検証にかかる時間は少なくとも証明にかかる時間程度であるが、PCPに属する言語ではその限りではない。従って、PCPについての証明はNPよりも長くなる可能性がある。
上記の解説では、検証者が神託機械に問い合わせできる回数の上限を特に設定していない。PCP系の能力に影響するもう1つの要因として、検証者が実施できるコイントス回数がある。また、コイントス回数が増えれば、検証者はより厳密に証明を検証できる。従って PCP は実際には、2つの引数を持つ関数でパラメータ化された複雑性クラスのメタクラスと言うことができる。
PCP(''r''(·), ''q''(·)) は、確率的検査可能証明のある言語のクラスであり、検証者は ''r''(''n'') 回のコイントスと ''q''(''n'') 回の神託機械への問い合わせが可能である（''n'' は入力長）。
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「PCP (計算複雑性理論)」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|